package com.lsa.letcode.the10.longestPalindromic;

public class Solution {
    public String longestPalindrome(String s) {
    	if (s.length() < 2) {
    		return s;
    	}
    	if (s.length() == 2) {
    		return s.charAt(0) == s.charAt(1)? s : s.substring(0, 1);
    	}
//        return longest(s, 0, s.length() - 1);
    	return longestDp2(s);
    }
    
    private static String longestDp2(String s) {
    	int len = s.length();
		boolean[] dp = new boolean[len * len];
    	for (int i = 0; i < len; i++) {
			dp[i + i * len] = true;
		}
    	int size = s.length();
		int maxFrom  = 0;
		int maxTo  = 0;
		for (int l = 2; l <= size; l++) {
			for (int i = 0; i < size - l + 1; i++) {
				int j =  l + i - 1;
				if (s.charAt(i) == s.charAt(j) && ((i+1 >= j-1) || dp[i+1 + len * (j-1)])) {
					maxFrom = i;
					maxTo = j;
					dp[i + len *j] = true;
				}
			}
		}
    	return s.substring(maxFrom, maxTo + 1);
    }
    
    @SuppressWarnings("unused")
    private static String longestDp(String s) {
    	boolean[][] dp = new boolean[s.length()][s.length()];
    	for (int i = 0; i < dp.length; i++) {
			dp[i][i] = true;
		}
    	int size = s.length();
		int maxFrom  = 0;
		int maxTo  = 0;
		for (int l = 2; l <= size; l++) {
			for (int i = 0; i < size - l + 1; i++) {
				int j =  l + i - 1;
				if (s.charAt(i) == s.charAt(j) && ((i+1 >= j-1) || dp[i+1][j-1])) {
					maxFrom = i;
					maxTo = j;
					dp[i][j] = true;
				}
			}
		}
    	return s.substring(maxFrom, maxTo + 1);
    }
    
    @SuppressWarnings("unused")
	private static String longest(String s, int from, int to) {
		int size = to - from + 1;
		int maxFrom  = 0;
		int maxTo  = 0;
		int maxLen = 1;
		for (int l = 2; l <= size; l++) {
			for (int i = from; i < size - l + 1; i++) {
				int j =  l + i - 1;
//				System.out.print(String.format("(%s,%s)", i, j));
				if (isPalindrome(s, i, j) && l > maxLen) {
					maxFrom = i;
					maxTo = j;
					maxLen = l;
				}
			}
//			System.out.println();
		}
		return s.substring(maxFrom, maxTo+1);
    }
    
    private static boolean isPalindrome(String s, int from, int to) {
    	if (from >= to) {
    		return true;
    	}
    	return s.charAt(from) ==  s.charAt(to) && isPalindrome(s, from+1, to-1);
    }
}